package leetcode_core.leetcode_4;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2022年10月22日 11:33
 */
public class JobScheduling {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        //将startTime和endTime合并为一个区间
        List<int[]> inteval = new ArrayList<>();
        //这里的话可以先填充一个占位符进去
        inteval.add(new int[]{-1,-1,-1});
        //接着就是将数组存进去
        int n = startTime.length;
        for(int i = 0;i<n;i++){
            inteval.add(new int[]{startTime[i],endTime[i],profit[i]});
        }
        //对区间进行排序,按照结束时间
        Collections.sort(inteval, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        //然后开始遍历该区间
        int[] dp = new int[n+1];
        dp[0] = 0;
        for(int i = 1;i<=n;i++){
            //然后就是找到一个合适的区域
            int target = inteval.get(i)[0];
            int pre=getIndex(inteval,target,i);
            dp[i] = Math.max(dp[i-1],dp[pre]+inteval.get(i)[2]);
            System.out.println(dp[i]+" "+pre);
        }
        return dp[n];
    }

    private int getIndex(List<int[]> intervals,int target,int end){
        int left = 1,right = end;
        //定义搜索区间为[left,right)
        //需要寻找的是右侧边界
        while (left<right){//结束条件是left==right,因此最终返回left或者right都可以
            int mid = left+(right-left)/2;
            int midNum = intervals.get(mid)[1];
            if(midNum == target){
                //寻找右侧边界,左侧边界向右边逼近
                left = mid+1;
            }else if(midNum > target){
                //已经检查过了mid,而mid是比target要大的
                right = mid;
            }else if(midNum < target){
                //已经检查过了mid,而mid是比target要小的,因此left
                left = mid+1;
            }
        }
        return left;
    }

}
